It is often desirable to verify the connectivity between two or more nodes of a computer network. Connectivity verification protocol exchanges, such as, e.g., Multi-Protocol Label Switching (MPLS) echo messages (“pings”), Internet Control Message Protocol (ICMP) echo messages/pings, bidirectional forwarding detection (BFD) messages, “hello” messages, etc., may be used to generate request/reply messages to verify such connectivity between the nodes. For instance, a first node may send an echo request to a second node, which upon receiving the request, may return an echo reply/response to the first node. Generally, these echo request/reply messages may be sent between the nodes using a transmission protocol, e.g., using the Internet Protocol (IP), Asynchronous Transfer Mode (ATM) signaling, etc., or tunnels established therein.
Broadly stated, a tunnel is a logical structure that encapsulates a packet (a header and data) of one protocol inside a field, e.g., a data field, of another protocol packet with a new header. In this manner, a tunnel creates a transparent virtual network link between two network nodes that is generally unaffected by physical network links or devices (i.e., the physical network links or devices merely forward the encapsulated packet based on the new header). By this broad definition, one example of a tunnel is any MPLS Label Switched Path (LSP), and other known tunneling methods include, inter alia, the Layer Two Tunnel Protocol (L2TP), the Point-to-Point Tunneling Protocol (PPTP), and IP tunnels. A packet that is forwarded within a tunnel may generally be considered to be “in-band”within the tunnel. Conversely, a packet not forwarded within that tunnel may be considered to be “out-of-band” from that tunnel. Therefore, a message (e.g., an echo request/reply message) that is sent within the tunnel is referred to as an “in-band” message, while a message not sent within the tunnel is referred to as an “out-of-band” message.
Traceroute techniques have been developed as an extension to echo requests in order to trace the route (path) that a packet traverses between two or more nodes. Conventionally, a traceroute is performed by sending echo requests from a source node to a destination node that have progressively longer time-to-live (TTL) values. For instance, a first echo request with a TTL of “1” may reach the first intermediate node between the source and destination (a “next-hop” node). When the first intermediate node receives the echo request, it decrements the TTL to “0”, and returns a message (e.g., an error message) to the source node (generally, with the address of the first intermediate node). The source node may then send a second echo request with a TTL of “2” that is received by the first intermediate node, which decrements the TTL to “1” and forwards the echo request to a second intermediate node (a “next-next-hop” node). The second intermediate node decrements the TTL to “0”, and also returns a message (e.g., an error message) to the source node. The source node may continue to send subsequent echo requests with increasing TTL values until the route between the source and destination has been traced.
Traceroute techniques may also be used with tunnels (e.g., MPLS Traceroute) in a similar manner. For instance, assume the source node is an ingress to a tunnel, and that the destination node is the tunnel egress. The source node injects in-band echo requests with increasing TTL values into the tunnel. As described above, each successive intermediate in-band node (hop) that receives an expired TTL echo request replies to the source node accordingly (e.g., with an out-of-band reply).
While a conventional tunnel is established between a source end node and a destination end node, i.e., a “point-to-point” (P2P) tunnel, a multipoint tunnel, on the other hand, may be employed that connects one or more source end points to one or more destination end points, e.g., along a shared tree. The multipoint tunnel may be used in a manner similar to (and may complement) IP multicast, with packet replication at various nodes of the shared tree, as will be understood by those skilled in the art. A “Point-to-Multipoint” (P2 MP) tunnel, for example, has one source end node (ingress node) to source traffic onto the P2 MP tunnel, and multiple destination end nodes (egress nodes) to receive the traffic from the P2 MP tunnel.
In a conventional P2 MP tunnel traceroute, it is expected that all nodes n hops away (i.e., where “n” is the initial TTL value) will reply. As trace progresses, therefore, an increasingly large number (e.g., potentially thousands) of replies may be generated as the P2 MP tree “branches” (expands) toward the multipoint egress nodes (leafs). The source node typically processes all of these replies, which may pose a processing burden for that node. In particular, because a failure is detected by a lack of response from a node, any replies that fail to be processed by the source node may result in improper failure determination (“false positives”). Also, in the event an actual failure is limited to a few leaf (egress) nodes, the use of conventional traceroute may become especially egregious, since the failure is most likely close to the egress nodes.